package algocasts;

public class P120_CountingBits {
    private int numberOfOne(int n) {
        int count = 0;
        while (n != 0) {
            ++count;
            n &= (n - 1);
        }
        return count;
    }

    // Time: O(n*k)  Space: O(1)
    public int[] countBits(int n) {
        int[] d = new int[n + 1];
        for (int i = 0; i <= n; i++)
            d[i] = numberOfOne(i);
        return d;
    }

    // Time: O(n)  Space: O(1)
    public int[] countBitsOn(int n) {
        int[] d = new int[n + 1];
        for (int i = 1; i <= n; i++)
            d[i] = d[i & (i - 1)] + 1;
        return d;
    }


}
